1. Field of the Invention
The present invention relates generally to the processing and display of images on a display screen in a computer graphics system. More particularly, an improved method of rendering polygons is provided which identifies nonconvex polygons given only a list of vertices.
2. Description of Related Art
There are three classes of polygons which must be rendered and drawn to a display in a computer graphics system (see FIG. 3). Convex polygons make up the simplest class to draw, since the outer boundary never crosses itself and will always turn in the same direction. This type of configuration guarantees that there will be exactly one filled span in the "y" direction of a Cartesian coordinate system, and that for every "y" value contained within the polygon between the minimum and maximum (top and bottom) will have a filled span. A filled span refers to a scan line of picture elements (pixels), contained within the polygon, which are illuminated on the display in a computer graphics system.
Nonconvex polygons are more complicated than convex polygons, because even though the perimeter never crosses itself (nonconvex polygons have a definite inside and outside), internal angles are included which are greater than 180 degrees. Therefore, when a nonconvex polygon is drawn, there may be two separate spans for any given "y" value. That is, a nonconvex polygon may have a concave portion which will create spans to be scan converted in the "y" direction on either side of the concave area.
Complex polygons are the most complicated types of polygons and correspondingly the most difficult to scan-convert because there is no definite inside and outside. The perimeter of complex polygons can turn in any direction and cross itself. Therefore, in addition to the problems of having potential multiple "y" scan lines in the polygon and having no span lines for some "y" scan lines, complex polygons also have the problem of having two ways to fill the polygon. That is, since there is no definite inside or outside, it must be determined which area of the polygon to fill.
Conventional methods of filling complex polygons include the "odd-even" rule and the "winding" rule (Computer Graphics: Principles and Practice, J. Foley, A. van Dam, S. Feiner and J. Hughes, Addison-Wesley, 1990, page 965). Rendering complex polygons is an extremely computational intensive process and requires a great deal more time and resources than rendering nonconvex or convex polygons. Generally, rendering complex polygons requires 10 times as must time as rendering nonconvex polygons.
In conventional graphics systems, such as X Window System (X Window System is a trademark of the Massachusetts Institute of Technology) a client program sends a hint about the class of polygon to be rendered. This hint must be conservative, in that the least optimistic class must be used to render the polygon correctly. That is, a hint cannot indicate a less complicated class of polygon than the class the polygon to be drawn is actually in. For example, with convex polygons, the X-client can provide hints to convex, nonconvex or complex polygons and the convex polygon will be drawn correctly. However, for nonconvex polygons, hints directed to nonconvex or complex polygons are the only ones that will ensure proper rendering of the polygons. Finally, hints for complex polygons are the only ones that will properly draw a complex polygon. It can be seen that if a hint regarding a convex polygon is provided to the X-server and the polygon actually being drawn is complex, the results will be undefined, since methods for rendering convex polygons do not apply to complex polygons, and the polygon will be drawn incorrectly.
There exists conventional methods for identifying convex polygons, given a set of vertices, such that the corresponding hint can be provided. It can readily be seen that a method of distinguishing complex polygons from nonconvex polygons would be extremely advantageous, since knowing the class of polygon would allow the most efficient means of rendering the polygons to be utilized. Thus, the current necessity of using the most complicated procedures to scan convert polygons can be eliminated such that rendering of nonconvex polygons can occur up to 10 times faster.